import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 * <p>
 * 注意：解集不能包含重复的组合。
 */
public class ArraySum2 {


    @Test
    public void test1() {
        int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};

        List<List<Integer>> result = combinationSum2(candidates, 8);

        List<Integer> r1 = Arrays.asList(1, 1, 6);
        List<Integer> r2 = Arrays.asList(1, 2, 5);
        List<Integer> r3 = Arrays.asList(1, 7);
        List<Integer> r4 = Arrays.asList(2, 6);
        Assertions.assertTrue(result.contains(r1));
        Assertions.assertTrue(result.contains(r2));
        Assertions.assertTrue(result.contains(r3));
        Assertions.assertTrue(result.contains(r4));
        Assertions.assertEquals(4, result.size());
    }


    @Test
    public void test2() {
        int[] candidates = new int[]{2, 5, 2, 1, 2};

        List<List<Integer>> result = combinationSum2(candidates, 5);

        List<Integer> r1 = Arrays.asList(1, 2, 2);
        List<Integer> r2 = Arrays.asList(5);

        Assertions.assertTrue(result.contains(r1));
        Assertions.assertTrue(result.contains(r2));

        Assertions.assertEquals(2, result.size());
    }


    @Test
    public void test3() {
        int[] arr = new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

        List<Integer> r1 = Arrays.asList(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);


        List<List<Integer>> result = combinationSum2(arr, 27);

        Assertions.assertTrue(result.contains(r1));

        Assertions.assertEquals(1, result.size());
    }


    @Test
    public void test4() {
        int[] arr = new int[]{14, 6, 25, 9, 30, 20, 33, 34, 28, 30, 16, 12, 31, 9, 9, 12, 34, 16, 25, 32, 8, 7, 30, 12, 33, 20, 21, 29, 24, 17, 27, 34, 11, 17, 30, 6, 32, 21, 27, 17, 16, 8, 24, 12, 12, 28, 11, 33, 10, 32, 22, 13, 34, 18, 12};

        List<Integer> r1 = Arrays.asList(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);


        List<List<Integer>> result = combinationSum2(arr, 27);

//        Assertions.assertTrue(result.contains(r1));

//        Assertions.assertEquals(1, result.size());

        for (List<Integer> integers : result) {
            System.out.println(integers);
        }
    }

    List<List<Integer>> result = new ArrayList<List<Integer>>();


    int[] candidates;


    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        Arrays.sort(candidates);

        this.candidates = candidates;

        find(target, new ArrayList<>(), 0);

        //        对结果进行排序，去重处理
        return result.stream().peek(Collections::sort).distinct().sorted((l1, l2) -> {
            return l1.iterator().next() - l2.iterator().next();
        }).collect(Collectors.toList());
    }

    boolean find(int target, List<Integer> previousResult, int excludeIndex) {

        if (target == 0) {
            this.result.add(previousResult);
            return true;
        } else if (target < 0) {
            return false;
        }

        for (int i = excludeIndex; i < candidates.length; i++) {

            int nextTarget = target - candidates[i];


            ArrayList<Integer> nextResult = new ArrayList<>(previousResult);
            nextResult.add(candidates[i]);

            boolean found = find(nextTarget, nextResult, i + 1);
        }

        return false;
    }


}
